class Solution {
public:

    string ip1;
    string ip2;
    string ip3;
    string ip4;

    bool validIp()
    {
        if(ip1.size()>3||ip2.size()>3||ip3.size()>3||ip4.size()>3)
            return false;
        if((ip1.size()==3&&ip1>"255")||(ip2.size()==3&&ip2>"255")||(ip3.size()==3&&ip3>"255")||(ip4.size()==3&&ip4>"255"))
            return false;
        if(ip1[0]=='0'&&ip1.size()>1)
        {
            return false;
        }
        if(ip2[0]=='0'&&ip2.size()>1)
        {
            return false;
        }
        if(ip3[0]=='0'&&ip3.size()>1)
        {
            return false;
        }
        if(ip4[0]=='0'&&ip4.size()>1)
        {
            return false;
        }
        return true;
    }



    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        function<void(int, int)> dfs = [&](int now_index, int now_ip)
        {
            if (now_ip == 5)
            {
                if (validIp() && now_index == s.size())
                {
                    result.push_back(ip1 + "." + ip2 + "." + ip3 + "." + ip4);
                }
                return;
            }
            for (int i = 1; i <= 3; i++)
            {
                if (now_index + i > s.size())
                    break;
                switch (now_ip)
                {
                case 1:
                    ip1 = s.substr(now_index, i);
                    break;
                case 2:
                    ip2 = s.substr(now_index, i);
                    break;
                case 3:
                    ip3 = s.substr(now_index, i);
                    break;
                case 4:
                    ip4 = s.substr(now_index, i);
                    break;
                }
                dfs(now_index + i, now_ip + 1);
                switch (now_ip)
                {
                case 1:
                    ip1 = "";
                    break;
                case 2:
                    ip2 = "";
                    break;
                case 3:
                    ip3 = "";
                    break;
                case 4:
                    ip4 = "";
                    break;
                }
            }
        };
        dfs(0, 1);
        return result;
    }
};